package com.zyk.grate_offer.class02;

import java.util.Arrays;
import java.util.TreeMap;

/**
 * 给定数组hard和money，长度都为N
 * hard[i]表示i号的难度， money[i]表示i号工作的收入
 * 给定数组ability，长度都为M，ability[j]表示j号人的能力
 * 每一号工作，都可以提供无数的岗位，难度和收入都一样
 * 但是人的能力必须>=这份工作的难度，才能上班
 * 返回一个长度为M的数组ans，ans[j]表示j号人能获得的最好收入
 *
 * @author zhangsan
 * @date 2021/4/23 11:22
 */
public class Code01_ChooseWork {

    // 贪心
    public static int[] getMoneys(int[] hard, int[] money, int[] ability) {
        Job[] jobs = new Job[hard.length];
        for (int i = 0; i < hard.length; i++)
            jobs[i] = new Job(hard[i], money[i]);

        // 排序 + 去重
        Arrays.sort(jobs, (a, b) -> a.hard != b.hard ? a.hard - b.hard : b.money - a.money);
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(jobs[0].hard, jobs[0].money);
        Job pre = jobs[0];
        for (int i = 0; i < jobs.length; i++) {
            if (jobs[i].hard != pre.hard && jobs[i].money > pre.money) {
                pre = jobs[i];
                map.put(pre.hard, pre.money);
            }
        }
        int[] ans = new int[ability.length];
        for (int i = 0; i < ability.length; i++) {
            Integer key = map.floorKey(ability[i]);
            ans[i] = key != null ? map.get(key) : 0;
        }
        return ans;
    }

    public static class Job {
        int hard, money;

        public Job(int hard, int money) {
            this.hard = hard;
            this.money = money;
        }
    }

    // for test
    public static void main(String[] args) {
        int[] hard = {1, 32, 2, 11, 31, 32, 21, 31, 32, 15, 15, 21, 51, 32, 1, 31, 31, 22, 132, 123};
        int[] money = {6, 21, 35, 64, 53, 31, 31, 32, 13, 15, 15, 15, 1, 16, 1, 16, 1, 61, 61, 61, 61, 6};
        int[] ability = {15,1,231,23,1,321,32,132,10,231,032,1032,1,0231,023,1023,102,1,032,032,1032,10,3210,321,03,1023,103};

        int[] ans = getMoneys(hard, money, ability);
        System.out.println(Arrays.toString(ans));
    }

}
